//
// Created by yangchao on 2022/6/9.
// 402. 移掉 K 位数字: https://leetcode.cn/problems/remove-k-digits/
//

#include <string>
#include <vector>
using namespace std;

//贪心+单调栈
class RemoveKdigits {
public:
    string removeKdigits(string num, int k) {
        vector<char> stk;
        for(auto& ch: num) {
            while (stk.size() > 0 && stk.back() > ch && k > 0) {
                stk.pop_back();
                k -= 1;
            }
            stk.push_back(ch);
        }
        while (k > 0) {
            stk.pop_back();
            --k;
        }
        string res = "";
        bool zeroSign = true;
        for(auto& digit: stk) {
            if (zeroSign && digit == '0') {
                continue;
            }
            zeroSign = false;
            res += digit;
        }
        return res == "" ? "0" : res;
    }
};

